home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8263 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: inferno.mpx.com.au!news
  2. From: Malcolm Smith <mjsmith@mpx.com.au>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 16 Feb 1996 07:46:59 GMT
  6. Organization: Microplex Pty Ltd
  7. Message-ID: <4g1cpj$3dd@inferno.mpx.com.au>
  8. References: <4fr8be$ass@news.iconn.net>
  9. NNTP-Posting-Host: dialup-211.mpx.com.au
  10.  
  11. thecrow@iconn.net (The Crow) wrote:
  12. >
  13. > Here is what I am trying to do, I want to find the last NON-ZERO digit of a 
  14. > given factorial.  For instance,
  15. > 
  16. > 5! = 120
  17. > 
  18. > so the last non-zero digit is 2.  I want to be able to do this up to 1000.  
  19. > Problem is, no matter how huge of a data-type you use, there isn't any way for 
  20. > the computer to handle 1000!, it is however possible to find the last non-zero 
  21. > digit somehow.  One thing I have tried is as I went through mulitplying the 
  22. > series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the 
  23. > trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i 
  24. > am not really sure why.  If anyone has a clue how I can do this let me know.
  25. > 
  26. > -- 
  27. > The Crow - thecrow@iconn.net
  28. > "It can't rain all the time"
  29. > -Kryptology
  30. > 
  31.  
  32.  
  33. Why not treat the numbers as strings.  There is a technique of
  34. multiplying numbers using a table.
  35.  
  36. Imagine multiplying 7658 x 453.  Form a table 4 x 3.
  37.  
  38.  
  39.  7  6  5  8
  40. +----------+
  41. |          | 4
  42. |          | 5
  43. |          | 3
  44. +----------+  
  45.  
  46. Draw horizontal and vertical lines for each column and row.  Next draw
  47. diagonal lines (/) between each sqaure.  Multiply each number (column
  48. by row) and insert the answers in each half of each sqaure.
  49.  
  50.             6
  51. e.g.,     +---+
  52.           |1 /|
  53.           | / | 3  
  54.           |/ 8|
  55.           +---+
  56.  
  57. When the table is complete you add the diagonal columns (from right
  58. to left) putting the last digit under the corresponding column and
  59. carry the remainder of the answer into the next column (to the left).
  60. (if the total was 156 put a 6 under the column and add 15 to the next
  61. diagonal on the left).
  62.  
  63. When you have finished adding the diagonal columns you will find the
  64. answer from left to right around the table.
  65.  
  66.        5   6
  67.      +---+---+
  68.      |1 /|1 /|
  69.    1 | / | / | 3          The answer is 168.
  70.      |/ 5|/8 |
  71.      +-------+
  72.        6   8
  73.  
  74.  
  75. You could treat all your numbers as strings, muliply them by using
  76. an array (or to save on memory you could evaluate each column as you
  77. go.
  78.  
  79. I don't have any code handy.  If you want some Email me and I'll try
  80. to find some time.  State whether you want to use an array or memory.
  81. The memory version will probably be slower because as the numbers
  82. grow it will be re-evaluating columns many times over.
  83.  
  84.  
  85.  
  86. Mal
  87. mjsmith@mpx.com.au
  88.  
  89.